def maxNumber(nums1, nums2, k):   # 从0到k遍历各自数组中找出最大的子序列,再合并成一个大的子序列,比较出最终的最大合并子序列
    def pick_k_max(nums, k):      # 从数组中选出k位最大的数
        stack = []
        remain_num = len(nums) - k
        for num in nums:
            while remain_num and stack and stack[-1] < num:
                stack.pop()
                remain_num -= 1
            stack.append(num)
        return stack[:k]

    def merge(A, B):              # 合并两个数组,组成一个大的数组
        res = []
        while A or B:
            bigger = A if A > B else B
            res.append(bigger[0])
            bigger.pop(0)         # 赋值后A,B会随着bigger的改变而改变
        return res

    ans = [0] * k
    for i in range(k + 1):        # 遍历k种情况,找出最大的值
        if i <= len(nums1) and k - i <= len(nums2):
            ans = max(ans, merge(pick_k_max(nums1, i), pick_k_max(nums2, k - i)))
    return ans

#算法测试
if __name__ == '__main__':
   print(maxNumber([3,4,6,5],[9,1,2,5,8,3],5))